Multi-Core Ant Colony Optimization for TSP in Erlang

This is a continuation of Parallel Ant Colony Optimization for TSP in Standard ML and Multi-Core Ant Colony Optimization for TSP in Haskell. See first page for Ant Colony and TSP problem description. Here the program has been rewritten in the programming language Erlang.

Erlang was originally developed by Ericsson for use in telecom switching devices. Recently SMP/multi-core support has been added. Erlang has lightweight processes and distributed message-based inter-process communication patterned after Hoare's CSP. Processes are created using the spawn() command, and messages are sent with the ! command and received with receive(). Unlike CSP and Concurrent ML, Erlang's messages are asynchronous. With this difference John Reppy considers Erlang to be an Actor language (Concurrent Programming in ML, p. 37). Concurrent Haskell also uses asynchronous messages.

My Erlang source code is here.

languagecitiesiterations (ants)corestime (secs)speedup
Erlang200100167.8
Erlang200100235.61.90
GHC Haskell200100110.2
GHC Haskell20010026.91.48
MLton Standard ML20010010.52
Alice Standard ML200100138.2

All tests were performed on AMD Athlon A64x2 (dual core) 4400 CPU (2.2 GHz), 2048Meg memory, Debian Linux 2.6.15-1-k7-smp, Erlang 5.5/OTP R11B, GHC 6.5.20060620 (compile: -threaded -O; runtime: +RTS -K500m -H1000m -N2), MLton 20060213-1. Alice-1.2-1 was tested on the same hardware booted with Windows XP Pro SP2, as the Debian Linux package requires an older version of libgmp3 (Multiprecision arithmetic library) which conflicts with MLton and probably GHC.

Erlang is much slower than the others. Erlang is a bytecode interpreted virtual machine while the others (except 2nd-slowest Alice) are native code compilers. Like Haskell, Erlang has immutable (single assignment) variables which force lots of copying. Unlike Standard ML and Haskell, no array type is provided so I had to inefficiently implement them using dictionaries. In Erlang each process (thread) does have a separate heap, so there is little interference between processes due to garbage collection. Near perfect speedup is achieved.

Here are some language comparisons:

language language type typing evaluation single assign- ment SMP / Multi- Core distrib- uted native compiled messaging
Alice Standard ML functionalstatic with type inferencestrict plus lazy futures--Yes-RPC
MLton Standard ML functionalstatic with type inferencestrict---Yessync
GHC Haskell functionalstatic with type inferencelazyYesYes(GpH with PVM)Yesasync
Erlang functionaldynamicstrictYesYesYes-async

Update

I've rerun the tests on an Intel Quad-Core. I've also revised the Erlang code based on blog reader suggestions.

Cores   Erlang   Haskell   SML
1       38.4     8.6       0.76
2       19.6     6.1
3       14.5     5.5
4       10.3     5.1
Revised Code:
Erlang
Haskell
MLton Standard ML

New details and results in Multi-Core Ant Colony Optimization for TSP in Scala